package com.zwj.interview.BFS;

import java.util.Stack;

/**
 * 给定一棵二叉搜索树，请调整节点的指针使每个节点都没有左子节点。调整之后的树看起来像一个链表，但仍然是二叉搜索树
 *
 * 重点：变成链表简单，但是还要是颗二叉树，那么原先某个节点的左节点就需要先遍历   按照左节点  当前节点  右节点的顺序遍历
 * 正好满足中序遍历
 */
public class 二叉搜索树变单链表 {

    /**
     * 中序遍历:左节点-->根节点-->右节点
     * 看起来需要按照节点的值递增的顺序遍历二叉搜索树中的每个节点，并将节点用指向右子节点的指针连接起来。
     * 这就容易让人联想到二叉树的中序遍历，只是在这里每遍历到一个节点要把前一个节点的指向右子节点的指针指向它
     *
     * @param root
     * @return 二叉搜索树变链表，对于任何一个节点，就是将其左节点的右指针指向它，它自己的右指针不变
     * 下面这个是转换成单链表，牛客网上是转成双链表
     */
    public TreeNode increasingBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack();
        TreeNode cur = root;
        TreeNode prev = null;
        TreeNode first = null;
        while (cur != null || !stack.isEmpty()) {
            //拿到最左边的节点，也就是这颗树中最小的节点
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            //变量prev表示前一个遍历到的节点。在遍历到当前节点cur时，把变量prev的右子节点的指针指向cur，
            // 并将cur指向左子节点的指针设为null
            if (prev != null) {
                prev.right = cur;
            } else {
                //这个first就是二叉树遍历到的第一个节点
                first = cur;
            }
            //推进prev指针
            prev = cur;
            //断开左边指针
            cur.left = null;
            //继续推进cur节点
            cur = cur.right;
        }
        return first;
    }



}
